#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;

class Solution {
public:

    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int init_d = image[sr][sc];
        queue<pair<int, int>> qu;
        qu.push(make_pair(sr, sc));
        map<pair<int, int>, int> hash;
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            hash[tmpPos]++;
            image[tmpPos.first][tmpPos.second] = color;
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int xx = dx[i] + tmpPos.first;
                int yy = dy[i] + tmpPos.second;
                if (xx < 0 || xx >= image.size() || yy < 0 || yy >= image[0].size())
                    continue;
                if (image[xx][yy] == init_d && !hash.count(make_pair(xx, yy))) {
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        return image;
    }
};


class Solution {
public:

    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int init_d = image[sr][sc];
        if (init_d == color) return image;
        queue<pair<int, int>> qu;
        qu.push(make_pair(sr, sc));
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            image[tmpPos.first][tmpPos.second] = color;
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int xx = dx[i] + tmpPos.first;
                int yy = dy[i] + tmpPos.second;
                if (xx < 0 || xx >= image.size() || yy < 0 || yy >= image[0].size())
                    continue;
                if (image[xx][yy] == init_d) {
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        return image;
    }
};

class Solution {
public:

    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int numIslands(vector<vector<char>>& grid) {

        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    queue<pair<int, int>> qu;
                    qu.push(make_pair(i, j));
                    grid[i][j] = '0';
                    while (!qu.empty()) {
                        pair<int, int> tmpPos = qu.front();
                        qu.pop();
                        for (int z = 0; z < 4; z++) {
                            int xx = tmpPos.first + dx[z];
                            int yy = tmpPos.second + dy[z];
                            if (xx >= 0 && xx < grid.size() && yy >= 0 && yy < grid[0].size() && grid[xx][yy] == '1') {
                                qu.push(make_pair(xx, yy));
                                grid[xx][yy] = '0';
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};


class Solution {
public:

    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    vector<vector<bool>> vis;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        vis.resize(grid.size());
        for (int i = 0; i < grid.size(); i++) {
            vis[i].resize(grid[i].size());
        }
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    ans = max(ans, bfs(grid, i, j));
                }
            }
        }
        return ans;
    }

    int bfs(vector<vector<int>>& grid, int x, int y)
    {
        int count = 1;
        queue<pair<int, int>> qu;
        qu.push(make_pair(x, y));
        vis[x][y] = true;
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            qu.pop();
            for (int k = 0; k < 4; k++) {
                int xx = tmpPos.first + dx[k];
                int yy = tmpPos.second + dy[k];
                if (xx >= 0 && xx < grid.size() && yy >= 0 && yy < grid[0].size()
                    && grid[xx][yy] == 1 && !vis[xx][yy]) {
                    vis[xx][yy] = true;
                    count++;
                    qu.push(make_pair(xx, yy));
                }
            }
        }
        return count;
    }
};

class Solution {
public:

    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[210][210];

    void solve(vector<vector<char>>& board) {
        int n = board.size();
        int m = board[0].size();
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O' && !vis[i][0])
                bfs(board, i, 0);
            if (board[i][m - 1] == 'O' && !vis[i][m - 1])
                bfs(board, i, m - 1);
        }
        for (int j = 1; j < m - 1; j++) {
            if (board[0][j] == 'O' && !vis[0][j])
                bfs(board, 0, j);
            if (board[n - 1][j] == 'O' && !vis[n - 1][j])
                bfs(board, n - 1, j);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && !vis[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    void bfs(vector<vector<char>>& board, int x, int y)
    {
        vis[x][y] = true;
        queue<pair<int, int>> qu;
        qu.push(make_pair(x, y));
        while (!qu.empty()) {
            pair<int, int> tmpPos = qu.front();
            qu.pop();
            for (int k = 0; k < 4; k++) {
                int xx = tmpPos.first + dx[k];
                int yy = tmpPos.second + dy[k];
                if (xx >= 0 && xx < board.size() && yy >= 0 && yy < board[0].size()
                    && board[xx][yy] == 'O' && !vis[xx][yy]) {
                    vis[xx][yy] = true;
                    qu.push(make_pair(xx, yy));
                }
            }
        }
    }
};